|
In computational geometry, the farthest-first traversal of a bounded metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, known as the greedy permutaton. Farthest-point traversals have many applications, including the approximation of the traveling salesman problem and the metric ''k''-center problem. They may be constructed in polynomial time, or (for low-dimensional Euclidean spaces) approximated in near-linear time. ==Properties== Fix a number ''k'', and consider the subset formed by the first ''k'' points of the farthest-first traversal of any metric space. Let ''r'' be the distance between the final point of the prefix and the set of previously-selected points. Then this subset has the following two properties: *All pairs of the selected points are at distance at least ''r'' from each other, and *All points of the whole metric space are at distance at most ''r'' from the subset. In other words, each prefix of the farthest-first traversal forms a Delone set.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Farthest-first traversal」の詳細全文を読む スポンサード リンク
|